#include "Heap.h"

void insert(MaxHeap *heap, int value) {
    if (heap->size == heap->capacity) {
        exit(EXIT_FAILURE);
    }
    heap->size++;
    heap->nodes[heap->size] = value;
    recursiveSiftUp(heap, heap->size);
}

void siftUp(MaxHeap *heap, int index) {
    while (index > 1) {
        if (heap->nodes[index] > heap->nodes[index / 2]) {
            swap(heap, index, index / 2);
        } else {
            break;
        }
        index /= 2;
    }
}

void recursiveSiftUp(MaxHeap *heap, int index) {
    if (heap->nodes[index] > heap->nodes[index / 2]) {
        swap(heap, index, index / 2);
        recursiveSiftUp(heap, index / 2);
    }
}

void swap(MaxHeap *heap, int indexA, int indexB) {
    int tmp = heap->nodes[indexA];
    heap->nodes[indexA] = heap->nodes[indexB];
    heap->nodes[indexB] = tmp;
}

void printData(MaxHeap* heap) {
    for (int i = 1; i <= heap->size; ++i) {
        printf("%4d |", heap->nodes[i]);
    }
    putchar('\n');
}

int getMax(MaxHeap *heap) {
    return heap->nodes[1];
}

int getSize(MaxHeap *heap) {
    return heap->size;
}

bool isEmpty(MaxHeap *heap) {
    return heap->size == 0;
}

int extractMax(MaxHeap *heap) {
    int maxValue = getMax(heap);
    removeNode(heap, 1);
    return maxValue;
}

void removeNode(MaxHeap *heap, int index) {
    heap->nodes[index] = heap->nodes[heap->size];
    heap->size--;
    siftDown(heap, index);
}

void siftDown(MaxHeap *heap, int index) {
    int swapIndex = 0;
    int left = index * 2;
    int right = index * 2 + 1;
    if (left <= heap->size && heap->nodes[left] > heap->nodes[index]) {
        swapIndex = left;
    }
    if (right <= heap->size && heap->nodes[right] > heap->nodes[swapIndex]) {
        swapIndex = right;
    }
    if (swapIndex != 0) {
        swap(heap, index, swapIndex);
        siftDown(heap, swapIndex);
    }
}

void siftDownV2(int *numbers,int count, int index) {
    int swapIndex = -1;
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    if (left < count && numbers[left] > numbers[index]) {
        swapIndex = left;
    }
    if (right < count && numbers[right] > numbers[swapIndex]) {
        swapIndex = right;
    }
    if (swapIndex != -1) {
        int tmp = numbers[index];
        numbers[index] = numbers[swapIndex];
        numbers[swapIndex] = tmp;
        siftDownV2(numbers, count, swapIndex);
    }
}

void heapify(int *numbers, int count) {
    for (int i = (count - 2) / 2; i >= 0; i--) {
        siftDownV2(numbers, count, i);
    }
}
